# include <iostream>
using namespace std;

// ---串的定长顺序存储结构---
#define MAXLEN 255      // 串的最大长度
typedef struct {
    char ch[MAXLEN+1];  // 存储串的一维数组 ch[0]不放内容， 从1到255
    int length;         // 串的当前长度
}SString;


// ---串的堆式顺序存储结构---
typedef struct {
    char *ch;   
    int length;
}HString;

// ---串的链式存储结构---
#define CHUNKSIZE 80
typedef struct Chunk {
    char ch[CHUNKSIZE];
    struct Chunk *next;
} Chunk;
typedef struct {
    Chunk *head, *tail;     // 串的头指针和尾指针
    int length;             // 串的当前长度
}LString;


// BF 算法 从pos位置开始
int Index_BF(SString S, SString T, int pos)
{
    // 返回模式T在主串S中第pos个字符开始第一次出现的位置。若不存在，则返回值0
    // 其中， T非空， 1 <=pos<=S.length
    int i = pos;
    int j = 1;
    
    while (i <= S.length && j <= T.length)
    {
        if (S.ch[i] == T.ch[j]) {++i, ++j;}
        else {i = i-j+2; j = 1;}
    }
    if (j > T.length)
        return i-T.length;  // 匹配成功
    else 
        return 0;       // 匹配失败
}

// BF算法 从第一个元素开始
int Index(SString S, SString T) {
    int i = 1;
    int j = 1;
    while (i <= S.length && j <= T.length) {
        if (S.ch[i] == T.ch[j]) { ++i; ++j;}//主串和子串依次匹配下一个字符
    	else {i = i-j+2; j = 1;}//主串、子串指针回溯重新开始下一次匹配
    }
    if (j >= T.length)	return i-T.length;	// 成功
    else return 0;	// 不成功
}

int strStr(const char * haystack, const char * needle){
    int i = 0;
    int j = 0;
    while (i <= strlen(haystack)-1 && j <= strlen(needle)-1) {
        if (haystack[i] == needle[j]) {
            ++i;
            ++j;
        }
        else {
            i = i - j + 1;
            j = 0;
        }
    } 
    if (j > (strlen(needle)-1))
        return i - strlen(needle);
    else
        return -1;
}

int main(void) 
{
    const char *haystack = "hello";
    const char * needle = "ll";
    int ans;
    ans = strStr(haystack, needle);
    cout << ans << endl;
}